Bijeções (Combinatória)
Uma função f:A \to B é uma bijeção (ou função bijetora) se ela possui as seguintes características: (i) Para a_1,a_2 \in A , se f(a_1)=f(a_2) , então a_1=a_2 . (ii) Para todo b \in B , existe a \in A tal que f(a)=b . Outras maneiras de vermos que uma função é bijetora é mostrarmos que ela possui inversa. Lembre-se que a inversa da função f:A \to B é a função g:B \to A tal que g(f(a))=a para todo a \in A e f(g(b))=b para todo b \in B . Você pode saber um pouco mais sobre bijeções aqui. Proposição Considere dois conjuntos quaisquer. Eles possuem a mesma quantidade de elementos se, e somente se, existe uma bijeção entre eles. Qual a Vantagem de Usarmos Bijeções? Imagine que você quer saber a quantidade de elementos de um conjunto A . Se você mostrar que existe uma bijeção entre A e um outro conjunto B , então basta contar a quantidade de elementos de B . Exemplo (Cone Sul 1997) Seja n um número natural, n>3 . Demonstrar que entre os múltiplos de 9 menores que 10^n há mais números com a soma de seus dígitos igual a 9(n-2) que números com a soma de seus dígitos igual a 9(n-1) . Solução: Vamos considerar uma função que leva \overline{a_k \dots a_1a_0} em \overline{(9-a_{n-1})\dots(9-a_k)\dots(9-a_1)(9-a_0)} (podemos considerar a_{n-1}=\dots=a_{k+1}=0 , caso o número tenha k algarismos). Esta função é bijetora, pois possui inversa (esta função é inversa dela mesma). Qual a vantagem de considerarmos esta função? A soma dos algarismos de \overline{a_k \dots a_1a_0} é 9(n-2) se, e somente se, a soma dos algarismos de \overline{(9-a_{n-1})\dots(9-a_k)\dots(9-a_1)(9-a_0)} é 18 . Assim, a quantidade de números menores que 10^n cuja soma é 9(n-2) é a mesma quantidade de números menores que 10^n cuja soma é 18 . E como contar este último? Basta ver que isto é equivalente a descobrirmos a quantidade de n -uplas (x_1,x_2,\dots,x_n) tais que x_1+x_2+\dots+x_n=18 e 0 \leq x_1,x_2,\dots,x_n \leq 9 . Se não houvesse a condição 0 \leq x_1,x_2,\dots,x_n \leq 9 , conseguiríamos calcular o número de soluções não negativas: seria igual a {n+17 \choose 18} (você pode ver mais sobre essa ideia aqui). Para podermos encontrar o número exato de soluções com esta condição, devemos tirar do total os casos em que existe algum x_i=k>9 (para algum i=1,2,\dots,n ). Observe que, dentre esses, só pode existir no máximo um deles que é maior que 9 (caso contrário a soma seria maior que 18 ). Quantas soluções existem tais que x_i=k para algum i=1,2,\dots,n ? Se existe i tal que x_i=k , então x_1+x_2+\dots+x_{i-1}+x_{i+1}+\dots+x_n=18-k. Existem n maneiras de escolhermos i tal que x_i=k e {n-2+18-k \choose n-2}={n+16-k \choose n-2} de escolhermos x_1,x_2,\dots,x_{i-1},x_{i+1},\dots,x_n . Desta forma, o número de n -uplas que possui algum x_i=k>9 é n.{n+16-k \choose n-2} , de onde segue que o número de n -uplas que possui algum x_i>9 é n.\displaystyle{\sum _{k=10}^{18}{n-k+6 \choose n-2}}=n\choose n-2}+{n+5 \choose n-2}+\dots+{n-2 \choose n-2}. Por uma propriedade de coeficientes binomiais, a expressão acima se transforma em n {n+7 \choose n-1}= n {n+7 \choose 8}. Desta forma, a quantidade de n -uplas em que x_i<9 para todo i=1,2,\dots,n é {n+17 \choose 18}-n.{n+7 \choose 8}. E quanto a quantidade de x tais que s(x)=9(n-1) ? Pelo mesmo raciocínio, isto é igual a quantidade de x 's tais que s(x)=9 e x<10^n . Isto é igual a quantidade de n -uplas (x_1,x_2,\dots,x_n) tais que x_1+x_2+\dots+x_n=9 . Esta quantidade é {n+8 \choose 9} . Para concluirmos, basta mostrarmos que para n>3 , vale {n+8\choose 9}<{n+17 \choose 18}-n{n+7 \choose 8}. Esta última desigualdade equivale a {n+8\choose 9}+n{n+7 \choose 8}<{n+17 \choose 18} \Leftrightarrow \frac{(n+8)!}{9!(n-1)!}+n\frac{(n+7)!}{8!(n-1)!}<\frac{(n+17)!}{18!(n-1)!} \Leftrightarrow \Leftrightarrow (n+7)!(10n+8)<\frac{9!(n+17)!}{18!}(*). Provemos por indução que (*) é válida para n \geq 2 . O caso n=2 é verdadeiro. Vamos supor que (*) seja válida para n=k , isto é, \frac{9!(k+17)!}{18!}>(k+7)!(10k+8). Provemos que (*) vale para n=k+1 . Com efeito, \frac{9!(k+17+1)!}{18!}=\frac{9!(k+18).(k+17)!}{18!}>(k+18)(k+7)!(10k+8). O problema termina se provarmos que (k+18)(k+7)!(10k+8) \geq (k+1+7)!(10(k+1)+8). Mas isto equivale a dizer que 188k \geq 98k. O que é sempre verdade, pois k é positivo. Exemplo (OBM 2002 - 3ª Fase - Nível 3) Definimos o diâmetro de um subconjunto não vazio de \{1,2,\cdots,n\} com a diferença entre seu maior elemento e seu menor elemento (em módulo). Calcule a soma dos diâmetros de todos os subconjuntos não vazios de \{1,2,\cdots,n\} . Solução: Ao invés de trabalhar com as diferenças de uma vez, faremos algo diferente. Considere m e M as somas dos elementos máximos e mínimos dos subconjuntos. Como o diâmetro de um conjunto é definido como a diferença entre seu máximo e seu mínimo, segue que o valor que estamos procurando é M-m . Vamos calcular cada um separadamente e depois subtrair. Comecemos com m . Para podermos calcular esta soma, basta sabermos quantas vezes um número é parcela dela. Tomemos k um inteiro com 1 \leq k \leq n . Ele vai aparecer na soma toda vez que for mínimo de algum subconjunto de \{1,2,\cdots,n\} . Isto vai acontecer quando os elementos que aparecerem junto de k (caso houver) estiverem nesta lista: k+1,k+2,\cdots,n . Ou seja, basta sabermos a quantidade de subconjuntos de \{k+1,k+2,\cdots,n\} . Como este conjunto tem n-(k+1)+1=n-k elementos, segue que existem 2^{n-k} subconjuntos em que k é o menor elemento, ou seja, esta é a quantidade de vezes que ele aparece na soma. Com isso, m=\displaystyle{\sum_{k=1}^n k \cdot 2^{n-k}}. E agora, como podemos nos livrar deste n-k ? Uma maneira interessante seria abrir e inverter o somatório: m=1 \cdot 2^{n-1}+2 \cdot 2^{n-2}+\cdots+(n-1) \cdot 2^1+n \cdot 2^0= =(n-0)\cdot 2^0+(n-1) \cdot 2^1+\cdots+(n-(n-2))\cdot 2^{n-2}+(n-(n-1))\cdot 2^{n-1}=\displaystyle{\sum_{k=0}^{n-1} (n-k) \cdot 2^k}. Para calcularmos isto, usaremos um método chamado Contagem Dupla. Vamos calcular a mesma coisa duas vezes e depois comparar os resultados. Devemos contar um objeto que apareça (n-k) \cdot 2^k (ou algo parecido). Neste caso, calcularemos os subconjuntos que possuem diâmetro k . Para determinarmos quantos são estes conjuntos, devemos escolher o mínimo (e neste caso, o máximo já estará determinado, pois se a for o mínimo, o máximo deverá ser a+k ) e também os elementos que deverão fazer parte do conjunto. Quais são os valores possíveis para o mínimo? Observe que a+k deve ser menor ou igual a n , ou seja, a \leq n-k , de onde segue que existem (n-k) valores para o mínimo. Além disso, dentro deste conjunto pode aparecer quaisquer números da lista a+1,a+2,\cdots,a+(k-1) . Como esta lista tem a+(k-1)-(a+1)+1=k-1 elementos, podemos escolher quais da lista irão para o conjunto de 2^{k-1} maneiras. Assim existem (n-k)\cdot 2^{k-1} subconjuntos de diâmetro k . Desta forma, a quantidade de subconjuntos de \{1,2,\cdots,n\} de diâmetros 1,2,\cdots,n é \displaystyle{\sum_{k=0}^{n-1} (n-k) \cdot 2^{k-1}}. Vamos contar isso de outra maneira. Os únicos subconjuntos de \{1,2,\cdots,n\} que possuem diâmetro zero são os unitários. Desta forma, para descobrirmos a quantidade de subconjuntos de \{1,2,\cdots,n\} de diâmetros 1,2,\cdots,n devemos retirar do total os conjuntos unitários e vazios, ou seja, esta quantidade é igual a 2^n-n-1. Por isso, \displaystyle{\sum_{k=1}^{n-1} (n-k) \cdot 2^{k-1}}=2^n-n-1. Mas não é bem este somatório que queríamos. Vamos multiplicar por 2 para fazer aparecer 2^k no somatório \displaystyle{\sum_{k=1}^{n-1} (n-k) \cdot 2^k}=2^{n+1}-2n-2. Para realmente fazermos aparecer o m no somatório, a soma deve ir de k=0 a n-1 . Por isto, vamos somar o termos correspondente a k=0 em ambos os lados, ou seja, n : \displaystyle{\sum_{k=0}^{n-1} (n-k) \cdot 2^k}=2^{n+1}-2n-2+n \Leftrightarrow m=2^{n+1}-n-2.(*) Calculemos agora M em função de m . Se soubermos o mínimo de um conjunto, conseguimos calcular o máximo dele? Não! Mas podemos agora usar as bijeções: vamos associar certos conjuntos. E as bijeções serão feitas de forma que se soubermos o mínimo de um conjunto, podemos saber o máximo do conjunto associado a ele. Vamos considerar a função f(x)=n+1-x que é do primeiro grau e, portanto, uma bijeção. Para cada conjunto A=\{a_1,a_2,\cdots,a_n\} , consideraremos o conjunto f(A)=\{n+1-a_1,n+1-a_2,\cdots,n+1-a_n\} . Se a for o menor elemento de A , então n+1-a será o maior elemento de f(A) . Observe que, como f é uma bijeção e A é subconjunto de \{1,2,\cdots,n\} se, e somente se, f(A) também é (você pode ver isto considerando que 1 \leq a \leq n se, e somente se, 1 \leq f(a) \leq n ), segue que a lista dos subconjuntos de \{1,2,\cdots,n\} e a lista dos conjuntos associados com a bijeção é a mesma. Desta forma, somar o máximo de todos os subconjuntos de \{1,2,\cdots,n\} equivale a somar o máximo dos conjuntos que obteremos após associarmos com uma bijeção (conforme descrevemos anteriormente). Com isso, se x_1,x_2,\cdots,x_t forem os mínimos dos subconjuntos não vazios de \{1,2,\cdots,n\} , segue que m=x_1+x_2+\cdots+x_t e além disso, os máximos dos conjuntos após associarmos as bijeções são n+1-x_1,n+1-x_2,\cdots,n+1-x_t . Desta forma, M=(n+1-x_1)+(n+1-x_2)+\cdots+(n+1-x_t). Observe que existem 2^n-1 parcelas, pois esta é a quantidade de subconjuntos não vazios de \{1,2,\cdots,n\} . Desta maneira, M=(n+1) \cdot (2^n-1)-(x_1+x_2+\cdots+x_t)=(n+1) \cdot (2^n-1)-m. Já que queremos M-m , vamos substrair m em ambos os lados da igualdade. M-m=(n+1) \cdot (2^n-1)-2m. Assim, por (*) , M-m=(n+1) \cdot (2^n-1)-2(2^{n+1}-n-2)=n \cdot 2^n+2^n-2^{n+2}+n+3= =n \cdot 2^n+2^n-2^n \cdot 2^2+n+3=(n+1-2^2) \cdot 2^n+n+3=(n-3) \cdot 2^n+n+3. Exemplo (Cone Sul 2004) Seja n um inteiro positivo. Chamamos C_n a quantidade de inteiros positivos x , menores que 10^n , tais que a soma dos dígitos de 2x é menor que a soma dos dígitos de x . Demonstre que C_n \geq \frac{4}{9}(10^n-1) . Solução: Considere s(x) a soma dos algarismos de x . Façamos um caso particular: n=1 . x 2x s(x) s(2x) s(2x) é menor que s(x) ? 1 2 1 2 Não 2 4 2 4 Não 3 6 3 6 Não 4 8 4 8 Não 5 10 5 1 Sim 6 12 6 3 Sim 7 14 7 5 Sim 8 16 8 7 Sim 9 18 9 9 Sim Vale dizer que x satisfaz as condições do enunciado se, e somente se, 9-x não satisfaz. Para valores maiores de n parece viável conjecturar que x satisfaz as condições do enunciado se e somente se 10^n-1-x não satisfaz. Em outras palavras, s(2x) Vamos escrever expressões para s(x) , s(2x) , s(10^n-1-x) e s(2(10^n-1-x)) . Seja x=\overline{a_ka_{k-1}\dots a_1a_0}= \displaystyle{\sum _{j=0}^{k}a_j10^j}, onde a_0,a_1,\dots,a_k são os algarismos de x . Então s(x)=\displaystyle{\sum _{j=0}^{k}a_j}. E quanto a s(2x) ? Observe que 2x=\displaystyle{\sum _{j=0}^{k}2a_j10^j}. Isto significa que os algarismos de 2x são 2a_0,2a_1,\dots,2a_k ? Não. Lembre-se que algarismos são números menores que 10 . Se a \in \{0,1,2,3,4\} , então 2a \in \{0,2,4,6,8\} . Ou seja, neste caso, 2a terá apenas um dígito. Já se a \in \{5,6,7,8,9\} , então 2a \in \{10,12,14,16,18\} . Aqui 2a terá dois dígitos, sendo que o dígito das dezenas será igual a 1 . Observe que a soma 2a_010^0+2a_110^1+\dots+2a_k10^k não tem nenhum "mais um". O que isto quer dizer? Que se colocarmos os números 2a_010^0,2a_110^1,\dots,2a_k10^k um embaixo do outro e fizermos a adição, não precisamos "emprestar" nenhum número da direita para a esquerda. Como podemos verificar que isto é verdade? Suponha que hora de fazermos esta soma, dois destes números, digamos, 2a_i10^i e 2a_j10^j tem dígitos não nulos nas t -ésimas posições (da direita para a esquerda) e i . Como 2a_i10^i e 2a_j10^j possuem no máximo os dois primeiros dígitos não nulos, então t=j=i+1 e 2a_i possui dois algarismos. Neste caso, dá para emprestar 1 ? Não! De fato, o dígito da t -ésima posição de 2a_i10^i será igual a 1 e o de 2a_j10^j será no máximo 8 . Com isso, a soma dos dígitos nesta posição será no máximo igual a 9 e não tem como emprestar 1 . E o que ganhamos com isso? Que s(2x)=\displaystyle{\sum _{j=0}^{k}s(2a_j)}. (*) Ainda falta calcularmos s(10^n-1-x) e s(2(10^n-1-x)) . Note que 10^n-1-x=\underbrace{99\ldots9}_{n\text{ algarismos}}-\overline{a_ka_{k-1}\dots a_1a_0}=\overline{\underbrace{99\ldots9}_{n-k-1\text{ algarismos}}(9-a_k)(9-a_{k-1})\dots(9-a_1)(9-a_0)}. Com isso, s(10^n-1-x)=9(n-k-1)+\displaystyle{\sum _{j=0}^{k}(9-a_j)}=9(n-k-1)+\displaystyle{\sum _{j=0}^{k}9}-\displaystyle{\sum _{j=0}^{k}a_j}= =9(n-k-1)+9(k+1)-s(x)=9n-s(x). (**) E quanto a s(2(10^n-1-x)) ? s(2(10^n-1-x))=s(2.9)(n-k-1)+\displaystyle{\sum _{j=0}^{k}s(2(9-a_j))}=9(n-k-1)+\displaystyle{\sum _{j=0}^{k}s(2(9-a_j))}.(***) Mas realmente dá para calcular isto? Precisamos nos perguntar quanto vale s(2(9-a)) . Isto dependerá de a . Se a \in \{0,1,2,3,4\} , então 9-a \in \{5,6,7,8,9\} e assim 2(9-a) tem dois algarismos. Assim, s(2(9-a))=2(9-a)-9=9-2a. Já se a \in \{5,6,7,8,9\} , então 9-a \in \{0,1,2,3,4\} e assim 2(9-a) tem apenas um algarismo. Desta forma, s(2(9-a))=2(9-a)=18-2a. O problema é que ao voltarmos em (**) , não sabemos qual algarismos é menor que 5 e qual não é. Por isso, precisamos pensar em uma estratégia. Observe o seguinte, se a \in \{0,1,2,3,4\} , então s(2a)=2a, enquanto se a \in \{5,6,7,8,9\} , então s(2a)=2a-9. Em ambos os casos, s(2a)+s(2(9-a))=9. Se somarmos (*) com (***) , s(2x)+s(2(10^n-1-x))=\displaystyle{\sum _{j=0}^{k}s(2a_j)}+9(n-k-1)+\displaystyle{\sum _{j=0}^{k}s(2(9-a_j))}= =\displaystyle{\sum _{j=0}^{k}s(2a_j)+s(2(9-a_j))}+9(n-k-1)=9(k+1)+9(n-k-1)=9n.(****) Se compararmos (**) com (****) : s(x)+s(10^n-1-x)=s(2x)+s(2(10^n-1-x)) \Leftrightarrow \Leftrightarrow s(x)-s(2x)=s(2(10^n-1-x))-s(10^n-1-x). Observe que o lado esquerdo da igualdade é positivo se, e somente se, o direito também é (pois os dois são iguais). Desta forma, s(2x)s(10^n-1-x). De certa forma, para todo x tal que s(2x) , existe um y correspondente tal que s(2y) . Por isso, devemos chamar as bijeções. Considere X_n = \{1 \leq x <10^n : s(2x) Y_n = \{1 \leq x <10^n : s(2x)>s(x)\} e Z_n = \{1 \leq x <10^n : s(2x)=s(x)\}. Existe uma correspondência entre os dois conjuntos. Tomemos f: X_n \to Y_n tal que f(x)=10^n-1-x . Observe que esta função é bijetora, pois toda função do 1º grau é bijetora. Desta forma, |X_n|=|Y_n| . Observe que C_n=|X_n| . Dá para falarmos alguma coisa sobre C_n ? Note que, como X_n , Y_n e Z_n são dois a dois disjuntos. X_n \cup Y_n \cup Z_n = \{1,2,\dots,10^n-1\} \Leftrightarrow |X_n|+|Y_n|+|Z_n|=10^n-1 \Leftrightarrow \Leftrightarrow |X_n|+|X_n|+|Z_n|=10^n-1 \Leftrightarrow C_n = \frac{10^n-1-Z_n}{2}. Assim, a desigualdade que o enunciado quer que provemos é equivalente a |Z_n| \leq \frac{10^n-1}{9}. Exploremos os elementos de A_n . Observe que s(x) \equiv x \pmod{9} s(2x) \equiv 2x \pmod{9}. Com isso, s(2x)=s(x) \Rightarrow s(2x) \equiv s(x) \pmod {9} \Leftrightarrow 2x \equiv x \pmod{9} \Leftrightarrow x \equiv 0 \pmod{9}. Desta maneira, Z_n \subset \{1 \leq x <10^n : x \equiv 0 \pmod{9}\}. Assim, |Z_n| \leq |\{1 \leq x <10^n : x \equiv 0 \pmod{9}\}|=\frac{10^n-1}{9}. Bibliografia * E. Lozansky, C. Rousseau : Winning Solutions, Springer-Verlag, New York, 1996.Categoria:MatemáticaCategoria:Combinatória